The communications industry is rapidly changing to adjust to emerging technologies and ever increasing consumer demand. This consumer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
Consumers and designers of these systems typically desire high reliability and may wish to provide communications services with a guaranteed quality of service. Although packet communications systems are very complex, they are typically built around the basic concept of receiving packets and placing them in appropriate input queues, switching and processing of these packets and placing them in appropriate output queues, then sending the packets from these output queues. Although simple in concept, the details of how to queue and schedule individual systems can be quite complex and is a subject of many research and development efforts.
For example, if all received packets are placed in a single queue (FIFO), then a packet cannot be removed from the queue until all other packets ahead of it are removed from the queue, which can impose a head-of-line blocking problem. This concept is easily demonstrated in the context of a grocery store: if all consumers must use a single checkout register, then a person with one item may have to wait in line (i.e., wait in the queue) behind a person with a large number of items and not be able to check out until all of these large number of items are processed. Thus, express lanes are provided in many grocery stores so that a class of consumers (e.g., those with a few items, i.e., that only requires minimal processing) will not have to wait behind other classes of consumers (e.g., those with a large number of items that requires substantial processing). Similarly, many communications systems provide multiple priorities of packet traffic, wherein received packets are classified and placed in queues corresponding to their classification. The packets are then removed from the queues based on one of an unlimited number of scheduling methodologies.
The grocery store example also demonstrates another queuing problem, which is that one consumer is affected by other consumers (e.g., consumers wait in line for their turns behind other consumers). Similarly, this variant of the queuing problem occurs when packets of multiple packet streams, often belonging to different consumers, are placed in a same queue. The latency delay of a particular packet belonging to a stream/consumer will be affected by the latency delay of other stream/consumer's packets ahead of the particular packet in a queue.
Therefore, many communications systems that receive packets from multiple subscribers will provide each subscriber with its own groups of input queues and output queues, with each group including one or more queues often differentiated by an associated class of service. This approach does not scale well. For example, if a communications systems has one million active subscribers and each of these subscribers requires two classifications of packet traffic (e.g., a high and low priority), then four million queues will be required (i.e., two million queues for the ingress traffic and two million queues for egress traffic). Thus, this approach can require substantial resources.
Systems can be capable of dynamically creating or assigning groups of queues to packet traffic when a packet stream becomes active (i.e., when there is a least one packet's worth of traffic being communicated); such a system would be designed with the belief that a predetermined number of its subscribers will not be sending any traffic at any given time in order to avoid implementing a system with a full contingent of queuing resources. In other words, the system would be designed with over-subscribed queues in that there are not enough queues for all potentially active devices.
However, this over-subscription of queues approach does not completely address nor solve a scalability problem for systems in which has a large number of concurrent active subscribers, such as in the fixed mobile convergence (FMC) environment, which typically uses a virtual private network (VPN) gateway terminating Internet Protocol Security (IPSec) tunnels from dual-mode cellular/WIFI devices (e.g., including phones). A substantial portion of these devices and their corresponding tunnels are typically active at all times, as a device continuously sends control, keep-alive, and/or data packets whether or not a voice conversation or data communication session exists, in order to keep the tunnel open and the device accessible from the network device (e.g., so the device can receive calls). Thus, unless the device is turned completely off, it is actively sending packets, and therefore, current approaches require each device to have its own group of queues in order to be able to schedule on a basis of per subscriber and per subscriber/class. As it is not unforeseeable to have hundreds of thousands or millions of active consumers at a time, such a network device requires substantial queuing resources.
FIG. 1 illustrates such an example prior art FMC environment in which devices 101 communicate via tunnels 107 provided by communication mechanism(s) 105 to network device 120. Network device 120 also communicates with other devices 102 (e.g., routers, other network and consumer devices, etc.) via communications mechanism(s) 108. Tunnel support mechanism 121 terminates packet tunnels 121, including enqueuing and dequeuing packets with packet queues 122, which are also accessed by network device functions 123 (e.g., control, schedulers, packet processors, switching mechanisms, service modules, etc.). Packet queues 122 include one queue per group of subscribers. Therefore, in order to support a large number of subscribers, packet queues 122 represent a substantial number of queues and resources therein to implement these queues. Also, as queues are currently shared among multiple subscribers, QoS at the individual subscriber level is typically not provided.